package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

/**
 * https://leetcode.com/problems/kth-smallest-element-in-a-bst/
 * bst中第k小
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC230 implements TreeProblem {
    int result = Integer.MAX_VALUE;

    public int kthSmallest(TreeNode root, int k) {
        rec(root, k);
        return result;
    }

    //中序遍历. 返回值为子树元素个数, 最终结果在全局变量result中
    public int rec(TreeNode root, int k) {
        int size = 1;
        if (root.left != null) {
            size += rec(root.left, k);
        }
        if (k == size) {
            result = root.val;
        }
        if (root.right != null) {
            size += rec(root.right, k - size);
        }
        return size;
    }

    public static void main(String[] args) {
        Integer[] a = {3, 1, 4, null, 2};
        TreeNode treeNode = TreeNode.arrayToTreeNode(a);
        System.out.println(new LC230().kthSmallest(treeNode, 1));
    }
}
